#include <vector>
#include <algorithm>
#include <iostream>
#include <limits.h>

using namespace std;

class Solution
{
public:
  int coinChange(vector<int> &coins, int amount)
  {
    if (0 == coins.size())
      return -1;
    target = amount;
    // dp(n): 目标金额为n时，所需的硬币数量
    sort(coins.begin(), coins.end());
    vector<int> memo(amount + 1);
    return dp(0, coins, memo);
  }

  int dp(int n, vector<int> &coins, vector<int> &memo)
  {
    // base case

    if (memo[n] != 0)
    {
      return memo[n];
    }
    if (target == n)
    {
      return 0;
    }
    if (n > target)
    {
      return -1;
    }
    // 求最小值，所以初始化为正无穷
    int res = INT_MAX;
    for (int i = 0; i < coins.size(); i++)
    {
      int num = dp(n + coins[i], coins, memo);
      if (num == -1)
      {
        continue;
      }
      res = min(res, num + 1);
    }

    memo[n] = (res == INT_MAX ? -1 : res);
    return memo[n];
  }

private:
  int target = 0;
};

int main()
{
  Solution solute;
  vector<int> nums = {1, 2, 5};
  int amount = 11;
  cout << solute.coinChange(nums, amount) << endl;

  return 0;
}